#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int DATE_TYPE;

typedef struct linklist
{
    DATE_TYPE data;
    struct linklist *pre;
    struct linklist *next;
} linknode, *plinklist;

//--------------------------函数声明--------------------------
// 创建一个空链表
plinklist list_Create();
// 获得指定位置的结点
plinklist list_get(plinklist H, int pos); // 通过pos 获得第pos个位置的结点
// 判断是否尾空链表
int empty(plinklist H);
// 头插
int list_head_insert(plinklist H, DATE_TYPE value);
// 尾插
int list_tail_insert(plinklist H, DATE_TYPE value);
// 指定位置插入
int list_insert(plinklist H, DATE_TYPE value, int pos); // 将value插入到第pos结点之前
// 销毁链表
int list_free(plinklist *H);
// 删除某一个位置上的结点
int list_delete(plinklist H, int pos);
// 删除value值所在的结点 dir:0 从后先前遍历  dir:1从前向后遍历
int list_delete_value(plinklist H, DATE_TYPE value, int dir);
// 修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(plinklist H, DATE_TYPE oldvalue, DATE_TYPE newvalue);
// 向前遍历链表
int list_show_forward(plinklist H);
// 向后遍历链表
int list_show_back(plinklist H);

int main(int argc, char const *argv[])
{
    plinklist head = list_Create();

    printf("头插\n");
    list_head_insert(head, 1);
    list_head_insert(head, 2);
    list_head_insert(head, 3);
    list_show_back(head);

    printf("尾插\n");
    list_tail_insert(head, 4);
    list_tail_insert(head, 5);
    list_tail_insert(head, 6);
    list_show_back(head);

    printf("向前遍历\n");
    list_show_forward(head);

    printf("修改数据\n");
    list_change_vlaue(head, 3, 33);
    list_show_back(head);
    list_change_vlaue(head, 0, 10);
    list_show_back(head);
    list_change_vlaue(head, 6, 66);
    list_show_back(head);

    printf("获得指定结点\n");
    plinklist t;
    t=list_get(head, 0);
    printf("位置:0   结点：%d\n",t->data);
    t=list_get(head, 1);
    printf("位置:1   结点：%d\n",t->data);
    t=list_get(head, 6);
    printf("位置:6   结点：%d\n",t->data);
    t=list_get(head, 7);
   // printf("位置:7   结点：%d\n",t->data);

    printf("指定位置插入\n");
    list_insert(head, 111, 1);
    list_show_back(head);
    list_insert(head, 666, 8);
    list_show_back(head);
    list_insert(head, 777, 0);
    list_show_back(head);

    printf("删除指定值的结点\n");
    list_delete_value(head,111,0);
    list_show_back(head);
    list_delete_value(head,666,0);
    list_show_back(head);
    list_delete_value(head,33,1);
    list_show_back(head);
    list_delete_value(head,1,1);
    list_show_back(head);

    printf("删除指定位置结点\n");
    list_delete(head, 0);
    list_show_back(head);
    list_delete(head, 1);
    list_show_back(head);
    list_delete(head, 5);
    list_show_back(head);

    printf("销毁\n");
    list_free(&head);

    return 0;
}

//--------------------------函数定义--------------------------
// 创建一个空链表
plinklist list_Create()
{
    plinklist head = (plinklist)malloc(sizeof(linknode));
    if (head == NULL)
    {
        printf("head malloc faild\n");
        return NULL;
    }
    head->data = 0;
    head->next = head;
    head->pre = head;

    return head;
}

// 获得指定位置的结点
plinklist list_get(plinklist H, int pos) // 通过pos 获得第pos个位置的结点
{
    if (empty(H))
    {
        return NULL;
    }
    if (pos < 1 && pos != 0)
    {
        printf("pos is error\n");
        return NULL;
    }
    if (pos == 0)
    {
        return H;
    }
    plinklist phead = H->next;
    int i = 1;
    while (phead != H)
    {
        if (i < pos)
        {
            phead = phead->next;
            i++;
        }
        else
        {
            break;
        }
    }
    if (phead == H)
    {
        printf("pos is large\n");
        return NULL;
    }
    return phead;
}

// 判断是否尾空链表
int empty(plinklist H)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == H)
    {
        printf("list is empty\n");
        return 1;
    }
    return 0;
}

// 头插
int list_head_insert(plinklist H, DATE_TYPE value)
{
    if (H == NULL)
    {
        return -1;
    }
    plinklist newnode = (plinklist)malloc(sizeof(linknode));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    newnode->data = value;
    newnode->next = newnode->pre = NULL;

    // 更新指针指向
    newnode->next = H->next;
    H->next->pre = newnode;
    H->next = newnode;
    newnode->pre = H;

    return 0;
}

// 尾插
int list_tail_insert(plinklist H, DATE_TYPE value)
{
    if (H == NULL)
    {
        return -1;
    }
    plinklist phead = H;
    while (phead->next != H)
    {
        phead = phead->next;
    }
    // 此时phead指向尾结点
    plinklist newnode = (plinklist)malloc(sizeof(linknode));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    newnode->data = value;
    newnode->next = newnode->pre = NULL;

    // 更新指针指向
    newnode->pre = phead;
    phead->next = newnode;
    newnode->next = H;
    H->pre = newnode;
    return 0;
}

// 指定位置插入
int list_insert(plinklist H, DATE_TYPE value, int pos) // 将value插入到第pos结点之前
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (pos < 1)
    {
        printf("pos is error\n");
        return -1;
    }
    plinklist phead;
    phead = list_get(H, pos - 1);

    plinklist newnode = (plinklist)malloc(sizeof(linknode));
    if (newnode == NULL)
    {
        printf("newnode malloc faild\n");
        return -1;
    }
    newnode->data = value;
    newnode->next = newnode->pre = NULL;

    // 更新指针指向
    newnode->next = phead->next;
    phead->next->pre = newnode;
    newnode->pre = phead;
    phead->next = newnode;
    printf("%d 位置  插入  %d\n", pos, value);
    return 0;
}

// 销毁链表
int list_free(plinklist *H)
{
    plinklist phead = (*H), qhead = (*H);
    while ((*H)->next != qhead)
    {
        *H = (*H)->next;
        printf("free:  %d\n", phead->data);
        memset(phead, 0, sizeof(linknode));
        free(phead);
        phead = (*H);
    }
    printf("free:  %d\n", phead->data);
    memset(phead, 0, sizeof(linknode));
    free(phead);
    return 0;
}

// 删除某一个位置上的结点
int list_delete(plinklist H, int pos)
{
    if (empty(H))
    {
        return -1;
    }
    if (pos < 1)
    {
        printf("删除的结点位置：%d\n", pos);
        printf("pos is error\n");
        return -1;
    }
    plinklist phead = H->next;
    int i = 1;
    while (phead != H)
    {
        if (i < pos)
        {
            phead = phead->next;
            i++;
        }
        else
        {
            break;
        }
    }
    if (phead == H)
    {
        printf("删除的结点位置：%d\n", pos);
        printf("pos is large\n");
        return -1;
    }
    printf("删除的结点位置：%d\n", pos);
    phead->next->pre = phead->pre;
    phead->pre->next = phead->next;
    memset(phead, 0, sizeof(linknode));
    free(phead);
    return 0;
}

// 删除value值所在的结点 dir:0 从后先前遍历  dir:1从前向后遍历
int list_delete_value(plinklist H, DATE_TYPE value, int dir)
{
    printf("删除%d",value);
    if (empty(H))
    {
        return -1;
    }
    plinklist phead=H->next;
    if(dir)
    {
        printf("从前向后遍历\n");
        while(phead!=H)
        {
            if(phead->data!=value)
            {
                phead=phead->next;
            }
            else
            {
                break;
            }
        }
        if(phead==H)
        {
            printf("not find value\n");
            return -1;
        }
        phead->next->pre=phead->pre;
        phead->pre->next=phead->next;
        return 0;
    }
    else
    {
        printf("从后向前遍历\n");
        plinklist phead=H->pre;
        while(phead!=H)
        {
            if(phead->data!=value)
            {
                phead=phead->pre;
            }
            else
            {
                break;
            }
        }
        if(phead==H)
        {
            printf("not find value\n");
            return -1;
        }
        phead->next->pre=phead->pre;
        phead->pre->next=phead->next;
        return 0;
    }
}

// 修改结点数据  找到原数据  修改为新数据
int list_change_vlaue(plinklist H, DATE_TYPE oldvalue, DATE_TYPE newvalue)
{
    if (empty(H))
    {
        return -1;
    }
    plinklist phead = H->next;
    while (phead != H)
    {
        if (phead->data != oldvalue)
        {
            phead = phead->next;
        }
        else
        {
            break;
        }
    }
    if (phead == H)
    {
        printf("将 %d 修改为 %d \n", oldvalue, newvalue);
        printf("not find value\n");
        return -1;
    }
    phead->data = newvalue;
    printf("将 %d 修改为 %d \n", oldvalue, phead->data);
    return 0;
}

// 向前遍历链表
int list_show_forward(plinklist H)
{
    if (empty(H))
    {
        return -1;
    }
    plinklist phead = H->pre;
    while (phead != H)
    {
        printf("%d\t", phead->data);
        phead = phead->pre;
    }
    printf("\n");
    return 0;
}

// 向后遍历链表
int list_show_back(plinklist H)
{
    if (empty(H))
    {
        return -1;
    }
    plinklist phead = H->next;
    while (phead != H)
    {
        printf("%d\t", phead->data);
        phead = phead->next;
    }
    printf("\n");
    return 0;
}
